package com.huangyi;
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        //外观数列
        class Solution {
            public String countAndSay(int n) {
                String ret = "1";
                for (int i = 2; i <= n; i++) {
                    ret = encode(ret); // 对上一次结果做 RLE，得到下一次
                }
                return ret;
            }

            // 对字符串做一次行程长度编码：连续段 -> (长度)(字符)
            private String encode(String s) {
                StringBuilder sb = new StringBuilder();
                int i = 0, n = s.length();
                while (i < n) {
                    char ch = s.charAt(i);
                    int j = i;
                    while (j < n && s.charAt(j) == ch) j++; // 扩展到该连续段的末尾
                    sb.append(j - i).append(ch);            // 追加“长度+字符”
                    i = j;                                  // 下一段
                }
                return sb.toString();
            }
        }

        //数青蛙
        class Solution2 {
            public int minNumberOfFrogs(String croakOfFrogs) {
                String t = "croak";
                int n = t.length();                // 5
                int[] hash = new int[n];           // hash[i]：处在第 i 阶段的青蛙数（i: c/r/o/a/k）
                Map<Character, Integer> index = new HashMap<>(5);
                for (int i = 0; i < n; i++) index.put(t.charAt(i), i);

                for (char ch : croakOfFrogs.toCharArray()) {
                    if (ch == 'c') {
                        // 先复用一只刚完成的青蛙（阶段 4），否则相当于新增一只
                        if (hash[n - 1] > 0) hash[n - 1]--;
                        hash[0]++; // 进入 'c' 阶段
                    } else {
                        Integer i = index.get(ch);
                        if (i == null || i == 0) return -1; // 非法字符或顺序错误
                        if (hash[i - 1] == 0) return -1;    // 前一阶段没人可转移
                        hash[i - 1]--;                       // 从前一阶段拿一只
                        hash[i]++;                           // 进入当前阶段
                    }
                }

                // 不能有未完成的青蛙（停在 c/r/o/a），否则不合法
                for (int i = 0; i < n - 1; i++) {
                    if (hash[i] != 0) return -1;
                }
                // 合法：所有青蛙都收尾在 'k' 阶段
                return hash[n - 1];
            }
        }
    }
}